1141A Game 23
题目描述
Polycarp plays "Game 23". Initially he has a number n and his goal is to transform it to m. In one move, he can multiply n by 2 or multiply n by 3. He can perform any number of moves.
Print the number of moves needed to transform n to m. Print -1 if it is impossible to do so.
It is easy to prove that any way to transform n to m contains the same number of moves (i.e. number of moves doesn't depend on the way of transformation).
Input
The only line of the input contains two integers n and m (1≤n≤m≤5⋅108).
Output
Print the number of moves to transform n to m, or -1 if there is no solution.
Examples
Input
120 51840
Output
7
Input
42 42
Output
0
Input
48 72
Output
-1
Note
In the first example, the possible sequence of moves is: 120→240→720→1440→4320→12960→25920→51840. The are 7 steps in total.
In the second example, no moves are needed. Thus, the answer is 0.
In the third example, it is impossible to transform 48 to 72.
题意分析
因为是全英文的题面,我选择了先看样例,又看到了提示,因为紧张加小激动我把题意理解错了。。。以为是个水题(对大佬是真水题吧)。题目要求就是输入两个数,问你从第一个数变成第二个数需要几步,变化的方法是乘以2或者乘以3,如果可以,输出步数,不可以的话就输出“-1”,听学长说是质因子分解,可是我不会(哈哈哈哈,以后会了再来试试。经过我跟小伙伴的一波探讨发现可以用第二个数对第一个数先求余,如果余数不为0,直接输出“-1”。余数如果为0,就对两数的商进行处理,除以三能除尽就一直除直到除不尽,再判断,如果除以二能除尽就一直除直到除不尽,每循环一次次数加一,最后都除不尽的时候需要在进行一次判断了看现在的商是不是1,如果不是则说明变化的过程中只有二和三是不够的,所以需要输出“-1”,反之输出次数即可。
代码实现
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll n,m,k,a,b; cin>>n>>m; if(m%n!=0) cout<<"-1"; ll s=0; if(m%n==0) { k=m/n; while(k%3==0) { k/=3; s++; } while(k%2==0) { k/=2; s++; } if(k!=1) { cout<<"-1"<<endl; return 0; } cout<<s; } cout<<endl; return 0; }